﻿#ifndef _SIMPLE_STL_ALGORITHM_
#define _SIMPLE_STL_ALGORITHM_
namespace simplestl{


	// --------------- Сортировка --------------- 
	// sort
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	// stable_sort  
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	// parital_sort
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	// parital_stable_sort  
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	// lower_bound
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class ForwardIterator, class T>
	ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value )
	{
		ForwardIterator it;
		iterator_traits<ForwardIterator>::distance_type count, step;
		count = distance(first,last);
		while (count>0)
		{
			it = first; step=count/2; advance (it,step);
			if (*it<value)                   // or: if (comp(*it,value)), for the comp version
			{ first=++it; count-=step+1;  }
			else count=step;
		}
		return first;
	}

	// upper_bound  
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class ForwardIterator, class T>
	ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )
	{
		ForwardIterator it;
		iterator_traits<ForwardIterator>::distance_type count, step;
		count = distance(first,last);
		while (count>0)
		{
			it = first; step=count/2; advance (it,step);
			if (!(value<*it))                 // or: if (!comp(value,*it)), for the comp version
			{ first=++it; count-=step+1;  }
			else count=step;
		}
		return first;
	}

	// nth_element
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class ForwardIterator, class T>
	bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value )
	{
		first = lower_bound(first,last,value);
		return (first!=last && !(value<*first));
	}

	// binary_search
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class ForwardIterator, class T>
	bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value )
	{
		first = lower_bound(first,last,value);
		return (first!=last && !(value<*first));
	}

	// merge
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class InputIterator1, class InputIterator2, class OutputIterator>
	OutputIterator merge ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2,
		OutputIterator result )
	{
		while (true) {
			*result++ = (*first2<*first1)? *first2++ : *first1++;
			if (first1==last1) return copy(first2,last2,result);
			if (first2==last2) return copy(first1,last1,result);
		}
	}

	// inplace_merge  
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	// todo :

	// partition
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/
	template <class BidirectionalIterator, class Predicate>
	BidirectionalIterator partition ( BidirectionalIterator first,
		BidirectionalIterator last, Predicate pred )
	{
		while (true)
		{
			while (first!=last && pred(*first)) ++first;
			if (first==last--) break;
			while (first!=last && !pred(*last)) --last;
			if (first==last) break;
			swap (*first++,*last);
		}
		return first;
	}

	// stable_partition  
	// todo :
	/** ---  --- 
	@brief .
	@brief 
	@param first	Итератор, обозначающий начало диапазона.
	@param last		Итератор, обозначающий конец диапазона (не входит в сам диапазон!).
	@param 
	@ingroup		modif
	*/

	// --------------- Операции с кучей --------------- 

	// --------------- Минимум/Максимум --------------- 
	template <class T> const T& min ( const T& a, const T& b ) {
		return (a<b)?a:b;     // or: return comp(a,b)?a:b; for the comp version
	}

	template <class T> const T& max ( const T& a, const T& b ) {
		return (b<a)?a:b;     // or: return comp(b,a)?a:b; for the comp version
	}

	// ------------------- Операции с множествами -------------------
	
	template <class InputIterator1, class InputIterator2>
	bool includes ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2 )
	{
		while (first1!=last1)
		{
			if (*first2<*first1) break;
			else if (*first1<*first2) ++first1;
			else { ++first1; ++first2; }
			if (first2==last2) return true;
		}
		return false;
	}

	template <class InputIterator1, class InputIterator2, class OutputIterator>
	OutputIterator set_union ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2,
		OutputIterator result )
	{
		while (true)
		{
			if (*first1<*first2) *result++ = *first1++;
			else if (*first2<*first1) *result++ = *first2++;
			else { *result++ = *first1++; first2++; }

			if (first1==last1) return copy(first2,last2,result);
			if (first2==last2) return copy(first1,last1,result);
		}
	}

	template <class InputIterator1, class InputIterator2, class OutputIterator>
	OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2,
		OutputIterator result )
	{
		while (first1!=last1 && first2!=last2)
		{
			if (*first1<*first2) ++first1;
			else if (*first2<*first1) ++first2;
			else { *result++ = *first1++; first2++; }
		}
		return result;
	}

	template <class InputIterator1, class InputIterator2, class OutputIterator>
	OutputIterator set_difference ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2,
		OutputIterator result )
	{
		while (first1!=last1 && first2!=last2)
		{
			if (*first1<*first2) *result++ = *first1++;
			else if (*first2<*first1) first2++;
			else { first1++; first2++; }

		}
		return copy(first1,last1,result);
	}

	template <class InputIterator1, class InputIterator2, class OutputIterator>
	OutputIterator
		set_symmetric_difference ( InputIterator1 first1, InputIterator1 last1,
		InputIterator2 first2, InputIterator2 last2,
		OutputIterator result )
	{
		while (true)
		{
			if (*first1<*first2) *result++ = *first1++;
			else if (*first2<*first1) *result++ = *first2++;
			else { first1++; first2++; }

			if (first1==last1) return copy(first2,last2,result);
			if (first2==last2) return copy(first1,last1,result);
		}
	}

	// --------------- Перестановки --------------- 
	/**
	*  @brief  Permute range into the next "dictionary" ordering.
	*  @param  first  Start of range.
	*  @param  last   End of range.
	*  @return  False if wrapped to first permutation, true otherwise.
	*
	*  Treats all permutations of the range as a set of "dictionary" sorted
	*  sequences.  Permutes the current sequence into the next one of this set.
	*  Returns true if there are more sequences to generate.  If the sequence
	*  is the largest of the set, the smallest is generated and false returned.
	*/
	template<typename _BidirectionalIterator>
	bool
		next_permutation(_BidirectionalIterator __first,
		_BidirectionalIterator __last)
	{
		// concept requirements
		__glibcxx_function_requires(_BidirectionalIteratorConcept<
			_BidirectionalIterator>)
			__glibcxx_function_requires(_LessThanComparableConcept<
			typename iterator_traits<_BidirectionalIterator>::value_type>)
			__glibcxx_requires_valid_range(__first, __last);

		if (__first == __last)
			return false;
		_BidirectionalIterator __i = __first;
		++__i;
		if (__i == __last)
			return false;
		__i = __last;
		--__i;

		for(;;)
		{
			_BidirectionalIterator __ii = __i;
			--__i;
			if (*__i < *__ii)
			{
				_BidirectionalIterator __j = __last;
				while (!(*__i < *--__j))
				{}
				std::iter_swap(__i, __j);
				std::reverse(__ii, __last);
				return true;
			}
			if (__i == __first)
			{
				std::reverse(__first, __last);
				return false;
			}
		}
	}

	/**
	*  @brief  Permute range into the next "dictionary" ordering using
	*  comparison functor.
	*  @param  first  Start of range.
	*  @param  last   End of range.
	*  @param  comp
	*  @return  False if wrapped to first permutation, true otherwise.
	*
	*  Treats all permutations of the range [first,last) as a set of
	*  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
	*  sequence into the next one of this set.  Returns true if there are more
	*  sequences to generate.  If the sequence is the largest of the set, the
	*  smallest is generated and false returned.
	*/
	template<typename _BidirectionalIterator, typename _Compare>
	bool
		next_permutation(_BidirectionalIterator __first,
		_BidirectionalIterator __last, _Compare __comp)
	{
		// concept requirements
		__glibcxx_function_requires(_BidirectionalIteratorConcept<
			_BidirectionalIterator>)
			__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
			typename iterator_traits<_BidirectionalIterator>::value_type,
			typename iterator_traits<_BidirectionalIterator>::value_type>)
			__glibcxx_requires_valid_range(__first, __last);

		if (__first == __last)
			return false;
		_BidirectionalIterator __i = __first;
		++__i;
		if (__i == __last)
			return false;
		__i = __last;
		--__i;

		for(;;)
		{
			_BidirectionalIterator __ii = __i;
			--__i;
			if (__comp(*__i, *__ii))
			{
				_BidirectionalIterator __j = __last;
				while (!__comp(*__i, *--__j))
				{}
				std::iter_swap(__i, __j);
				std::reverse(__ii, __last);
				return true;
			}
			if (__i == __first)
			{
				std::reverse(__first, __last);
				return false;
			}
		}
	}

	/**
	*  @brief  Permute range into the previous "dictionary" ordering.
	*  @param  first  Start of range.
	*  @param  last   End of range.
	*  @return  False if wrapped to last permutation, true otherwise.
	*
	*  Treats all permutations of the range as a set of "dictionary" sorted
	*  sequences.  Permutes the current sequence into the previous one of this
	*  set.  Returns true if there are more sequences to generate.  If the
	*  sequence is the smallest of the set, the largest is generated and false
	*  returned.
	*/
	template<typename _BidirectionalIterator>
	bool
		prev_permutation(_BidirectionalIterator __first,
		_BidirectionalIterator __last)
	{
		// concept requirements
		__glibcxx_function_requires(_BidirectionalIteratorConcept<
			_BidirectionalIterator>)
			__glibcxx_function_requires(_LessThanComparableConcept<
			typename iterator_traits<_BidirectionalIterator>::value_type>)
			__glibcxx_requires_valid_range(__first, __last);

		if (__first == __last)
			return false;
		_BidirectionalIterator __i = __first;
		++__i;
		if (__i == __last)
			return false;
		__i = __last;
		--__i;

		for(;;)
		{
			_BidirectionalIterator __ii = __i;
			--__i;
			if (*__ii < *__i)
			{
				_BidirectionalIterator __j = __last;
				while (!(*--__j < *__i))
				{}
				std::iter_swap(__i, __j);
				std::reverse(__ii, __last);
				return true;
			}
			if (__i == __first)
			{
				std::reverse(__first, __last);
				return false;
			}
		}
	}


}
#endif //_SIMPLE_STL_ALGORITHM_
